package main.面试金典第六版;

import java.util.*;

public class Interview10 {
    public static void main(String[] args) {
        System.out.println("面试题10.01：合并排序的数组");
        System.out.println("面试题10.02：变位词组");
        System.out.println("面试题10.03：搜索旋转数组");
        System.out.println("面试题10.05：稀疏数组搜索");
        System.out.println("面试题10.09：排序矩阵查找");
        System.out.println("面试题10.10：数字流的秩");
        System.out.println("面试题10.11：峰与谷");
    }
}

class Interview_10_01{
    public void merge(int[] A, int m, int[] B, int n) {
        int index=A.length-1;
        for (int i=0;i<B.length;i++) A[index-i]=B[i];
        Arrays.sort(A);
    }
}

class Interview_10_02{
    public List<List<String>> groupAnagrams(String[] strs) {
        char[][] words=new char[strs.length][];
        for (int i=0;i< words.length;i++) words[i]=strs[i].toCharArray();
        for (int i=0;i< words.length;i++) Arrays.sort(words[i]);
        Map<String,List<String>> map=new HashMap<>();
        for (int i=0;i< words.length;i++) {
            String curStr=new String(words[i]);
            if (map.containsKey(curStr)) {
                List<String> list = map.get(curStr);
                list.add(strs[i]);
            }else {
                List<String> list=new ArrayList<>();
                list.add(strs[i]);
                map.put(curStr,list);
            }
        }
        List<List<String>> result=new ArrayList<>();
        for (String key: map.keySet()) {
            result.add(map.get(key));
        }
        return result;
    }
}

class Interview_10_03{
    public int search(int[] arr, int target) {
        int result=-1;
        for (int i=0;i<arr.length;i++) {
            if (arr[i]==target) {
                result=i;
                break;
            }
        }
        return result;
    }
}

class Interview_10_05{
    public int findString(String[] words, String s) {
        int result=-1;
        for (int i=0;i< words.length;i++) {
            if (words[i].equals(s)) {
                result=i;
                break;
            }
        }
        return result;
    }
}

class Interview_10_09{
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i=0;i<matrix.length;i++) {
            if (matrix[i].length==0) continue;
            int left=0,right=matrix[0].length-1;
            if (matrix[i][left]<=target&&matrix[i][right]>=target) {
                while (left<=right) {
                    int mid=left+(right-left)/2;
                    if (matrix[i][mid]==target) return true;
                    if (matrix[i][mid]<target) left=mid+1;
                    else right=mid-1;
                }
            }
        }
        return false;
    }
}

class Interview_10_10{
    TreeMap<Integer,Integer> map;
    public Interview_10_10() {
        map=new TreeMap<>();
    }

    public void track(int x) {
        if (!map.containsKey(x)) map.put(x,1);
        else {
            int temp=map.get(x)+1;
            map.put(x,temp);
        }
    }

    public int getRankOfNumber(int x) {
        int result=0;
        for (Integer key : map.keySet()) {
            if (key<=x) {
                result=result+map.get(key);
            }
        }
        return result;
    }
}

class Interview_10_11{
    public void wiggleSort(int[] nums) {
        int[] clone = nums.clone();
        Arrays.sort(clone);
        int left=(nums.length-1)/2,right=nums.length-1;
        for (int i=0;i< nums.length;i++) {
            nums[i]= i%2==0 ? clone[left--] : clone[right--];
        }
    }
}